import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Test {

    public static void mapPao(int[] arr){
        for(int i =0;i<arr.length-1;i++){
            for(int j = 0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int tmp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
        }
    }


    public static void insertSort(int[] arr){
        for(int i =1;i<arr.length;i++){
            for(int j =i-1;j>=0;j--){
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
        }
    }

    public static void minSort(int[] arr){
        for(int i =0;i<arr.length;i++){
            int min = i;

            for(int j =i+1;j<arr.length;j++){
                if(arr[j]<arr[min]){
                    min = j;
                }
            }

            int tmp =arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }

    public static void xiErSort(int[] arr,int gap){

        for(int i =gap;i<arr.length;i++){
            for(int j =i-gap;j>=0;j=j-gap){
                if(arr[j]>arr[j+gap]){
                    int tmp =arr[j];
                    arr[j]=arr[j+gap];
                    arr[j+gap] = tmp;
                }
            }
        }
    }

    public static void xiEr(int[] arr){

        int grap = arr.length/2;
        while(grap>0){
                xiErSort(arr,grap);
                grap/=2;
        }
    }


    public static void quickSort(int[] arr,int left,int right){
        if(left>=right){
            return;
        }

        int prior = partion(arr,left,right);
        quickSort(arr,left,prior);
        quickSort(arr,prior+1,right);
    }

    private static int partion(int[] arr, int left, int right) {

        int prior = arr[left];

        while(left<right){
            while(left<right&&arr[right]>prior){
                right--;
            }
         arr[left] = arr[right];

            while(left<right&&arr[left]<prior){
                left++;
            }
        arr[right] = arr[left];
        }
        arr[left] = prior;
        return left;
    }


    public static int[] merge(int arr[],int left,int right){

        if(left==right){
            return new int[]{arr[left]};
        }

        int mid = left+ (right-left)/2;

        int[] leftArr = merge(arr,left,mid);
        int[] rightArr = merge(arr,mid+1,right);

        int[] lastArr = hebing(leftArr,rightArr);
        return  lastArr;
    }

    private static int[] hebing(int[] leftArr, int[] rightArr) {
        int m = leftArr.length;
        int n = rightArr.length;
        int[] newArr = new int[m+n];
        int k = 0;
        int leftX = 0;
        int rightY = 0;

       while(leftX<m&&rightY<n){
           if(leftArr[leftX]<rightArr[rightY]){
               newArr[k] = leftArr[leftX];
               leftX++;
           }else{
               newArr[k] = rightArr[rightY];
               rightY++;
           }
           k++;
       }

       if(leftX<m){
           while(leftX<m){
               newArr[k] = leftArr[leftX];
               leftX++;
               k++;
           }
       }
       if(rightY<n){
           while(rightY<n){
               newArr[k] = rightArr[rightY];
               rightY++;
               k++;
           }
       }
       return  newArr;
    }


    public static void main(String[] args) {
    /*    int[] arr = new int[]{9,8,7,6,5,4,3,2,1};
        mapPao(arr);
        System.out.println(Arrays.toString(arr));*/
        int[] arr = new int[]{9,8,7,5,4,1,2,4};
       int[] tmp = merge(arr,0,arr.length-1);
        System.out.println(Arrays.toString(tmp));

        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
        Iterator<Integer> iterator1 = Arrays.stream(arr).iterator();
        while (iterator1.hasNext()){
            System.out.println(iterator1.next());
        }

    }
}
